package com.shawn.leetcode.array.one;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <a href="https://leetcode.com/problems/3sum/">3 sum</a>
 *	question description
 * <p>
 *  Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0?
 *  Find all unique triplets in the array which gives the sum of zero.
 * 	Note:
 *
 * 		The solution set must not contain duplicate triplets.
 *
 * 	Example:
 *
 * 		Given array nums = [-1, 0, 1, 2, -1, -4],
 *
 * 	A solution set is:
 * 	[
 *   	[-1, 0, 1],
 *   	[-1, -1, 2]
 * 	]
 * </p>
 * @author shawn
 */
public class ThreeSum {

	private static final int DEFAULT_LENGTH = 3;

	/**
	 * a + b + c = 0  --> one: a = 0,b = 0,c = 0
	 * 				  --> two: There must be a negative number between the abc
	 *
	 * 1. Arrays.sort(); -4 -1 -1 0 1 2
	 * 2. search negative number  -4
	 * 3. two point: head,tail head = i + 1,tail = n - 1;
	 *
	 * O(n^2)
	 *
	 * @param nums
	 * @return
	 */
	public List<List<Integer>> threeSum(int[] nums) {
		List<List<Integer>> result = new ArrayList<>();
		if(nums == null || nums.length < DEFAULT_LENGTH){
			return result;
		}
		// sort
		Arrays.sort(nums);

		int length = nums.length;
		// loop
		for (int i = 0; i < length; i++) {
			int num = nums[i];
			// look up negative num
			if(num > 0){
				break;
			}
			// remove duplicate num
			if(i > 0 && num == nums[i - 1]){
				continue;
			}

			// two point
			int head = i + 1;
			int tail = length - 1;
			int value = 0 - num;

			while (head < tail){
				int data = nums[head] + nums[tail];
				if(data == value){
					result.add(Arrays.asList(num,nums[head],nums[tail]));
					// continue
					while (head < tail && nums[tail] == nums[tail - 1]){
						 tail --;
					}
					while (head < tail && nums[head] == nums[head + 1]){
						head ++;
					}
					tail --;
					head ++;
				}else if(data > value){
					tail --;
				}else if(data < value){
					head ++;
				}
			}

		}
		return result;
	}

	public static void main(String[] args) {
		ThreeSum sum = new ThreeSum();
		int[] nums = {-1, 0, 1, 2, -1, -4};
		List<List<Integer>> lists = sum.threeSum(nums);
		lists.stream().forEach(list -> {
			list.stream().forEach(num -> {
				System.out.print(num + "\t");
			});
			System.out.println();
		});
	}

}
